package com.zs.letcode.top_interview_questions;

import java.util.Objects;

/**
 * 排序链表
 * 给你链表的头结点head，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * 进阶：
 * <p>
 * 你可以在O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 * 示例 3：
 * <p>
 * 输入：head = []
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 链表中节点的数目在范围[0, 5 * 104]内
 * -105<= Node.val <= 105
 * 相关标签
 * 排序
 * 链表
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa262d/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/5 10:23
 */
public class Chapter36 {
    public static void main(String[] args) {
        Chapter36 chapter36 = new Chapter36();
        chapter36.test();
    }

    private void test() {

    }

    /**
     * Definition for singly-linked list.
     */
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private class Solution {
        /**
         * 方法一：自顶向下归并排序
         */
        public ListNode sortList(ListNode head) {
            return sortList(head, null);
        }

        private ListNode sortList(ListNode head, ListNode tail) {
            if (Objects.isNull(head)) {
                return null;
            }
            if (head.next == tail) {
                head.next = null;
                return head;
            }
            ListNode slow = head, fast = head;
            while (fast != tail) {
                slow = slow.next;
                fast = fast.next;
                if (fast != tail) {
                    fast = fast.next;
                }
            }
            ListNode mid = slow;
            ListNode list1 = sortList(head, mid);
            ListNode list2 = sortList(mid, tail);
            ListNode sorted = merge(list1, list2);
            return sorted;
        }

        private ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummyHead = new ListNode(0);
            ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
            while (Objects.nonNull(temp1) && Objects.nonNull(temp2)) {
                if (temp1.val <= temp2.val) {
                    temp.next = temp1;
                    temp1 = temp1.next;
                } else {
                    temp.next = temp2;
                    temp2 = temp2.next;
                }
                temp = temp.next;
            }
            if (Objects.nonNull(temp1)) {
                temp.next = temp1;
            } else if (Objects.nonNull(temp2)) {
                temp.next = temp2;
            }
            return dummyHead.next;
        }

        /**
         * 方法二：自底向上归并排序
         */
        public ListNode sortList1(ListNode head) {
            if (Objects.isNull(head)) {
                return null;
            }
            int length = 0;
            ListNode node = head;
            while (Objects.nonNull(node)) {
                length++;
                node = node.next;
            }
            ListNode dummyHead = new ListNode(0, head);
            for (int subLength = 0; subLength < length; subLength <<= 1) {
                ListNode prev = dummyHead, curr = dummyHead.next;
                while (Objects.nonNull(curr)) {
                    ListNode head1 = curr;
                    for (int i = 0; i < subLength && Objects.nonNull(curr.next); i++) {
                        curr = curr.next;
                    }
                    ListNode head2 = curr.next;
                    curr.next = null;
                    curr = head2;
                    for (int i = 0; i < subLength && Objects.nonNull(curr.next); i++) {
                        curr = curr.next;
                    }
                    ListNode next = null;
                    if (Objects.nonNull(curr)) {
                        next = curr.next;
                        curr.next = null;
                    }
                    ListNode merged = merge(head1, head2);
                    prev.next = merged;
                    while (Objects.nonNull(prev.next)) {
                        prev = prev.next;
                    }
                    curr = next;
                }
            }
            return dummyHead.next;
        }
    }
}
